/**
 * @author hewei
 * @version 1.0
 * @description: 1144. 递减元素使数组呈锯齿状
 * @date 2022/11/3 21:07
 */

public class MovesToMakeZigzag {

    public int movesToMakeZigzag(int[] nums) {
        int count1 = 0, count2 = 0, n = nums.length;
        int[] temp1 = new int[n], temp2 = new int[n];
        temp2[0] = nums[0];
        for (int i = 0; i < n; i++) {
            int b = i + 1 < n ? nums[i + 1] : 0;
            if (i % 2 == 0) {
                int a = i - 1 >= 0 ? temp1[i - 1] : 0;
                count1 += Math.max(0, a - nums[i] + 1) + Math.max(0, b - nums[i] + 1);
                if (i + 1 < n) temp1[i + 1] = Math.min(nums[i] - 1, nums[i + 1]);
            } else {
                int a = temp2[i - 1];
                count2 += Math.max(0, a - nums[i] + 1) + Math.max(0, b - nums[i] + 1);
                if (i + 1 < n) temp2[i + 1] = Math.min(nums[i] - 1, nums[i + 1]);
            }
        }
        return Math.min(count1, count2);
    }
}
